This invention relates to video compression, and more particularly to decoder pipelines having coefficient prediction.
One fast-growing area of development is video transmission and compression. Video data can greatly enhance the quality of a computing experience. The consumer use of the Internet took off once graphics was linked to earlier text-based web pages. Portable consumer devices such as cell phones and personal digital assistant (PDA's) are being equipped with small cameras to allow for capture of still or even video pictures. Efficient transmission of captured images over limited-bandwidth links requires some sort of compression of the images.
A number of video-compression techniques are known. Compression standards, such as those developed by the motion-picture-experts group (MPEG), have been widely adopted. These compression techniques are lossy techniques, since some of the picture information is discarded to increase the compression ratio. However, compression ratios of 99% or more have been achieved with minimal noticeable picture degradation.
Next-generation compression standards have been developed for transmitting video over wireless networks. The MPEG-4 standard provides a robust compression technique for transmission over wireless networks. Recovery can occur when parts of the MPEG-4 bit stream is corrupted.
These MPEG standards ultimately break the image up into small 16×16 pixel macroblocks or even smaller 8×8 pixel blocks. Each block can then be compressed more or less independently of other blocks, and movement of blocks can be described as highly compressed “motion vectors” rather than large bitmaps of pixels.
FIG. 1 shows an image frame divided into rows and columns of blocks. The MPEG standard uses a divide-and-conquer technique in which the video sequence is divided into individual image frames known as video object planes (VOPs), and each frame is divided into rows and columns of macroblocks. Each macroblock is a rectangle of 16 by 16 pixels. Each macroblock can be further divided into 8×8 blocks.
Various window sizes and image resolutions can be supported by MPEG standards. For example, one common format is an image frame of 176 by 144 pixels. The image frame is divided into 18 rows of 8×8 blocks, with each row having 22 blocks each of 8×8 pixels. A total of 396 blocks are contained in each frame.
The blocks are arranged in a predetermined order, starting in the upper left with the first block (BLK #0). The second block, BLK #1, is to the right of BLK #0 in the first row, followed by blocks #2 to BLK #21 in the first row. The second row contains BLK #22 to BLK #43. The last row contains BLK #374 to BLK #395. Of course, other image sizes and formats can have the blocks in rows of various lengths, and various numbers of rows.
When an image frame is encoded, each block is encoded in macroblock-order, starting with the first macroblock of four blocks BLK #0,1 in the first row, and BLK #22, 2 3 in the second row, continuing to BLK #20, 21 in the first row and BLK# 42, 43 in the second row, and on until the last two rows to BLK #395. The blocks are arranged in the bit stream into one or more video packets (VP) with a header. In this example Y values of pixels are shown.
FIG. 2A shows an 8×8 block of pixels. Pixels can have components, such as luminance Y values and U, V chrominance values. An 8×8 pixel block may have 64 Y values but only half or one-quarter as many U or V values. FIG. 2A shows an 8×8 array of pixel values for block N. Each pixel is identified by its block number, column, and row. Thus pixel P(55,2,6) is the pixel at the second column of the sixth row of block 55. The 8×8 blocks can be Y values or U or V values, but only half as many rows and columns exist for U and V values for some common YUV formats.
FIG. 2B shows an 8×8 block of quantized DCT coefficients. After motion compensation blocks are compressed. During compression, the block of 8×8 pixel values shown in FIG. 2A is transformed from the spatial into the frequency domain using a transform such as a discrete cosine transform (DCT). The result of the DCT is an 8×8 array of coefficients. The DCT coefficients are designated D(b,c,r), where b is the block #, c is the column #, and r is the row #.
The DCT coefficients D(b,c,r) are then scaled or quantized by a quantization parameter Q. For example, when Q is 6, DCT coefficient values between 0 and 5 can be scaled to 0, while values between 6 and 11 are scaled to 6. These scaled values can be level-shifted by half the scale: 0 is shifted to 3, while 6 is shifted to 9. Since 12 input values (0-11) are reduced to 2 output value (3,9), compression occurs during quantization. Quantization changes the DCT coefficients D(b,c,r) into quantized DCT coefficients E(b,c,r). The quantized DCT coefficients E(b,c,r) are sometimes referred to as AC coefficients, except for the first coefficient E(b,0,0), which is known as the DC coefficient.
Although there are the same number and arrangement of quantized coefficients as pixels, there is not a one-to-one correspondence of coefficient values to pixel values. Pixel P(12,4,3) does not directly correspond to coefficient E(12,4, 3), even though they have the same position in block 12's array. A pixel cannot be generated from only the coefficient at the same position. Instead, many coefficients are needed to re-generate a pixel value using an inverse DCT.
In general, coefficients in one block do not have much correlation to coefficients in other blocks. However, the first row and column of coefficients does show some correlation to other blocks. The very first (DC) coefficient E(N,0,0) is unique to each block. However, other “alternating-current” (AC) coefficients in the first row and first column show correlation to coefficients in other blocks. These first-row and first-column coefficients are known as A.C. coefficients, and can be predicted using a technique known as adaptive AC coefficient prediction. D.C. coefficients can be predicted by another mechanism.
FIG. 3A shows correlation of first-row AC coefficients with the first row of the block above. A current block N has a first row of DCT coefficients E(N,0,0), E(N,1,0), E(N,2,0), E(N,3,0) . . . E(N,7,0). The first coefficient is E(N,0,0). The remaining coefficients E(N,1,0), E(N,2,0), E(N,3,0) . . . E(N,7,0) in block N often show a correlation to the first-row coefficients in the block above, block N-L, where L is the number of rows (22 in this example). Thus the first-row AC coefficients E(N,1,0), E(N,2,0), E(N,3,0) . . . E(N,7,0) in block N often show some correlation to the first-row AC coefficients E(N-22,1,0), E(N-22,2,0), E(N-22,3,0) . . . E(N-22,7,0) in the above block N-22.
The first-row AC coefficients E(N, 1,0), E(N,2,0), E(N,3,0) . . . E(N,7,0) in block N can be differentially coded as differences from the first-row AC coefficients E(N-22,1,0), E(N-22,2,0), E(N-22,3,0) . . . E(N-22,7,0) in block N-L, improving compression since the difference values require fewer bits than do full coefficient values. During de-compression, block N's first row coefficients E(N,1,0), E(N,2,0), E(N,3,0) . . . E(N,7,0) can be generated from E(N-22,1,0), E(N-22,2,0), E(N-22,3,0) . . . E(N-22,7,0).
FIG. 3B shows correlation of first-column AC coefficients with the first column of the previous block to the left. A current block N has a first column of DCT coefficients E(N,0,0), E(N,0,1), E(N,0,2), E(N,0,3) . . . E(N,0,7). The first coefficient E(N,0,0) is predicted using another mechanism, but the remaining coefficients E(N,0,1), E(N,0,2), E(N,0,3) . . . E(N,0,7) in block N often show a correlation to the first-column coefficients in the prior above, block N1. Thus the first-column AC coefficients E(N,0,1), E(N,0,2), E(N,0,3) . . . E(N,0,7) in block N often show some correlation to the first-column AC coefficients E(N-1,0,1), E(N-1,0,2), E(N-1,0,3) . . . E(N-1,0,7) in the prior block N-1. The first-column coefficients for block N can be coded as differences with the first-column coefficients in block N-1 and later re-generated during de-compression using AC prediction.
FIG. 4 is a block diagram of a prior-art decoder that performs AC prediction between the variable-length decoder and the inverse-quantizer. Parser 20 receives an MPEG-compressed bit-stream and extracts an AC prediction flag for the current block. When the AC prediction flag is false, no AC prediction is performed. Instead, mux 19 selects the decoded G(j,k) output from variable-length decoder 10. Variable-length decoder 10 receives the 8×8 block's coefficients from parser 20 and decodes the block's portion of the bit-stream using a variable-length decoding. For example, common coefficient values can be coded with a few bits while uncommon coefficient values can be coded as longer bit codes.
The decoded G(j,k) coefficients selected by mux 19 are the quantized DCT coefficients E(j,k), where j is the column and k is the row for the coefficient in the current block N. Inverse-quantizer 14 performs the inverse of the scaling and quantization step performed by the encoder, using the quantization parameter Qe that parser 20 extracts from the bit-stream. The quantization parameter Qe can be different for different blocks, or can be the same for all blocks in a frame. Inverse-quantizer 14 generates the reconstructed DCT coefficients D(j,k). Inverse DCT 16 performs an inverse DCT operation on the on all coefficients in the 8×8 block at one time. D(j,k) coefficients to generate the reconstructed pixel values P(j,k) for the block. The pixel values can be stored or displayed.
When the AC prediction flag is true, AC prediction is performed. Mux 19 selects the predicted quantized DCT coefficients G(j,k) from the lower input rather than the bit-stream quantized DCT coefficients G(j,k) from variable-length decoder 10. Adder 22 generates the predicted quantized DCT coefficients G(j,k) by adding an adjusted stored coefficient to the bit-stream quantized DCT coefficients G(j,k), which contain a differential value.
Quantized DCT coefficients from prior blocks are stored by coefficient store 18. The quantized DCT coefficients E(j,k) for the first row and for the first column of each current block are copied to coefficient store 18. Later, these stored coefficients can be read from coefficient store 18 as the prior block (N-1) or above block's (N-L) stored coefficients. The prior blocks' quantization parameters Qf are also stored.
The stored coefficients from coefficient store 18 must be adjusted since the quantization parameters for the current and prior blocks may be different. The stored coefficients for the prior block (either block above N-L or block to the left N-1) is read from coefficient store 18 and multiplied by the stored quantization parameter Qf for the prior block by multiplier 26. The result of multiplier 26 is then divided by the current block's quantization parameter Qe using divider 24. Divider 24 can be an integer divider that rounds to the nearest integer. Half-integer values are rounded away from zero.
Multiplier 26 and divider 24 thus correct the stored coefficient from coefficient store 18 for the differing quantization parameters. Multiplier 26 and divider 24 adjust the stored coefficients by a ratio of Qf to Qe. The adjusted stored coefficient is then added by adder 22 to the bit-stream quantized DCT coefficients G(j,k), generating the predicted quantized DCT coefficients G(j,k). Mux 19 selects the predicted quantized DCT coefficients for the first row or first column and sends these to inverse-quantizer 14.
The overall effect of AC prediction is to generate the reconstructed quantized DCT coefficients for the first row or column:E=G+(F*Qf)//Qe, 
where F is the stored coefficient from coefficient store 18 and // represents integer division with integer rounding away from zero. Other rows and columns are passed through the upper input of mux 19:E=G
While such an AC predictor is useful, such AC prediction is performed between variable-length decoder 10 and inverse-quantizer 14. This precludes a simple unified variable-length decoder and inverse-quantizer. What is desired is a unified variable-length decoder and inverse-quantizer stage. A unified variable-length decoder and inverse-quantizer is desired that still allows for AC prediction.